
#ifndef _CRY_PARTICLE_LIST_H_
#define _CRY_PARTICLE_LIST_H_
#pragma once

#include "Allocator.h"

namespace ParticleListNS
{
	ILINE bool TestPtrValidity(void* pointerToTest)
	{
		assert(pointerToTest != NULL);
		return true;
	}
}

#define for_all_ptrs(Type, p, cont) \
	for (Type* p = (cont).begin(), *p##_e = (cont).end(), *p##_next; (p != p##_e) && ParticleListNS::TestPtrValidity((void*)p) && ((p##_next = (cont).next(p)) || true); p = p##_next)

#define for_rev_all_ptrs(Type, p, cont) \
	for (Type* p = (cont).rbegin(), *p##_e = (cont).rend(), *p##_prev; (p != p##_e) && ParticleListNS::TestPtrValidity((void*)p) && ((p##_prev = (cont).prev(p)) || true); p = p##_prev)

////////////////////////////////////////////////////////////////////////
// Bidirectional list

template< class T, class TAlloc = StdAllocator >
class ParticleList
{
protected:

	struct Node: T
	{
		Node*	pNext;
		Node*	pPrev;

		Node() {}

		template<typename I>
		Node(I const& i)
			: T(i) {}
				
	};

	TAlloc m_Alloc;

public:

	typedef T value_type;

	// Constructors, using default allocator or allocator initialiser.
	ParticleList()
		{ reset(); }

	template<class I>
	ParticleList(const I& init)
		: m_Alloc(init)
		{ reset(); }

	~ParticleList()
		{ clear(); }

	bool operator +() const
		{ return head() != NULL; }
	bool operator !() const
		{ return head() == NULL; }
	bool empty() const
		{ return head() == NULL; }

	CONST_VAR_FUNCTION( T& front(),
		{ assert(!empty()); return *head(); } )
	CONST_VAR_FUNCTION( T& back(),
		{ assert(!empty()); return *tail(); } )
	ILINE void PrefetchLink( const T* link ) const
		{ PrefetchLine(link, sizeof(T));	}

	// Slow: do not call often
	size_t size() const
	{
		return m_nSize;
	}

	//
	// Iteration
	//
	CONST_VAR_FUNCTION( T* begin(),
		{ return head(); } )
	CONST_VAR_FUNCTION( T* end(),
		{ return NULL; } )
	ILINE static T* next(const T* p)
		{ return p ? get_node(p)->pNext : NULL; }

	CONST_VAR_FUNCTION( T* rbegin(),
		{ return tail(); } )
	CONST_VAR_FUNCTION( T* rend(),
		{ return NULL; } )
	static T* prev(const T* p)
		{ return p ? get_node(p)->pPrev : NULL; }

	//
	// Add elements
	//
	void* push_back_new()
	{
		Node* pNode = (Node*)m_Alloc.Allocate(pNode);
		if (pNode)
		{
			if (m_pTail) 
				m_pTail->pNext = pNode;
			pNode->pPrev = m_pTail;
			pNode->pNext = NULL;
			m_pTail = pNode;
			if (!m_pHead) 
				m_pHead = pNode;
			assert(tail() == pNode);
			m_nSize += 1;
		}
		return pNode;
	}

	T* push_back()
	{
		void* pNewNodeMemory = push_back_new();
		if (pNewNodeMemory)
			new(pNewNodeMemory) Node();
		return (T*)pNewNodeMemory;
	}

	void* push_front_new()
	{
		Node* pNode = (Node*)m_Alloc.Allocate(pNode);
		if (pNode)
		{
			if (m_pHead) 
				m_pHead->pPrev = pNode;
			pNode->pNext = m_pHead;
			pNode->pPrev = NULL;
			m_pHead = pNode;
			if (!m_pTail) 
				m_pTail = pNode;
			assert(head() == pNode);
			m_nSize += 1;
		}
		return pNode;
	}

	T* push_front()
	{ 
		void* pNewNodeMemory = push_front_new();
		if (pNewNodeMemory)
			new(pNewNodeMemory) Node();
		return (T*)pNewNodeMemory;
	}

	//
	// Remove elements
	//
	void erase(T* p)
	{
		Node* pNode = get_node(p);
		
		if(  pNode == m_pHead && pNode == m_pTail) // only node in list
		{
			m_pHead = NULL;
			m_pTail = NULL;
		}
		else if( pNode == m_pHead ) // node is head node
		{
			m_pHead = pNode->pNext;
			m_pHead->pPrev = NULL;
		}
		else if( pNode == m_pTail ) // node is tail node
		{
			m_pTail = pNode->pPrev;
			m_pTail->pNext = NULL;
		}
		else // somewhere in the middel of the list
		{
			pNode->pPrev->pNext = pNode->pNext;
			pNode->pNext->pPrev= pNode->pPrev;
		}
		Delete(m_Alloc, pNode);	
		m_nSize -= 1;
	}

	void pop_back()
	{
		assert(!empty());
		erase(tail());
	}

	void pop_front()
	{
		assert(!empty());
		erase(head());
	}

	void clear()
	{
		// Destroy all elements, in reverse order
		for (Node* p = tail(); p != NULL; )
		{
			Node* pPrev = p->pPrev;
			Delete(m_Alloc, p);
			p = pPrev;
		}
		reset();
	}

	template<class TSizer>
	void GetMemoryUsagePlain( TSizer* pSizer ) const
	{
		pSizer->AddObject(this, size() * sizeof(Node));
	}

	template<class TSizer>
	void GetMemoryUsage( TSizer* pSizer ) const
	{
		for_all_ptrs (const T, p, *this)
		{
			if (pSizer->AddObject(p, sizeof(Node)))
				p->GetMemoryUsage(pSizer);				
		}
	}

protected:

	Node*	m_pHead;
	Node* m_pTail;

	uint32 m_nSize;
protected:
	
	CONST_VAR_FUNCTION( Node* head(),
		{ return m_pHead; } )
	CONST_VAR_FUNCTION( Node* tail(),
		{ return m_pTail; } )

	void reset()
	{
		m_pHead = m_pTail = NULL;
		m_nSize = 0;
	}

	static Node* get_node(T* p)
	{
		Node* pNode = static_cast<Node*>(p);
		return pNode;
	}
	static const Node* get_node(const T* p)
	{
		const Node* pNode = static_cast<const Node*>(p);
		return pNode;
	}

};

#endif // _CRY_PARTICLE_LIST_H_
